/**
 *
 */
package BPlusTreeIndex;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.TreeMap;

/**
 * * B+树实体类<br> 负责创建和查找节点<br>
 *
 * @version 0.5<br>
 * @author kocio
 */
public class BTree<T> {

    private Node<T> root;
    private Node<T> Current;
    private TreeMap<T, ArrayList<Integer>> value;
    private int m;

    /**
     *
     * @param map 数据源(TreeMap类型)
     * @param m 阶数
     * @throws BTreeException B+Tree异常
     */
    public BTree(TreeMap<T, ArrayList<Integer>> map, int m) {
        this.m = m;
        this.value = map;
        ArrayList<Node<T>> nodelist = new ArrayList<Node<T>>(map.size());
        ArrayList<Node<T>> _nodelist = new ArrayList<Node<T>>(map.size());
        Node<T> node = null;
        Iterator it = map.keySet().iterator();
        int count = map.size();
        while (it.hasNext()) {
            Key<T> key = new Key(it.next());
            nodelist.add(new Node<T>(key, m));
        }
        while (count > (m)) {
            node = new Node<T>();
            int i = 0;
            for (Node _node : nodelist) {
                i++;
                _node.setParent(node);
                Key<T> key = (Key<T>) _node.getKey().get(0);
                node.addChilden(key, _node);
                if (i % m == 0) {
                    _nodelist.add(node);
                    node = new Node<T>();
                }
            }
            count = _nodelist.size();
            nodelist = (ArrayList<Node<T>>) _nodelist.clone();
            _nodelist = new ArrayList<Node<T>>(map.size());
        }
        while (count > 1) {
            node = new Node<T>();
            int i = 0;
            for (Node _node : nodelist) {
                i++;
                _node.setParent(node);
                Key<T> key = (Key<T>) _node.getKey().get(0);
                node.addChilden(key, _node);
            }

        _nodelist.add(node);
        count=_nodelist.size();

        }
        this.root = _nodelist.get(0);
    }

    private void outPrint() {
        int Count = 0;
        this.Current = this.root;
        while (Current.hasNext()) {
            for (int i = 0; i < this.Current.getKey().size(); i++) {
                System.out.println(Count++);
                this.Current = this.Current.getChilden().get(i);
            }
        }
    }

    /**
     * 关键字检索
     *
     * @param KeyWords 关键字
     * @return 查询结果ID
     */
    public ArrayList<Integer> Search(Key<T> KeyWords) {
        this.Current = this.root;
        int lastResult=1;
        while (this.Current.getChilden().get(0).hasNext()) {
            for (int i = 0; i < this.Current.getKey().size(); i++) {
                Key<T> temp = this.Current.getKey().get(i);
                int result = KeyWords.compareTo(temp);
                System.out.println(KeyWords);
                System.out.println(result);
                System.out.println(temp);
                if (result == 0) {
                    this.Current = this.Current.getChilden().get((i));
                } else if (result < 0&&lastResult>0) {
                	if(i!=0)
                    {this.Current = this.Current.getChilden().get((i-1));
                    break;
                    }
                	else
                	{
                		return new ArrayList<Integer>(0);
                	}
                } else if (lastResult<0){
                 //   this.Current = this.Current.getChilden().get((i));
                    //break;
                }
                lastResult = result;
            }
        }
        ArrayList<Integer> Result = new ArrayList<Integer>();
        ArrayList<Key<T>> keyList=new ArrayList<Key<T>>();
        
        for (Key<T> key : this.Current.getKey()) {
        	keyList.add(key);
        }
        Collections.sort(keyList);
        
        for (Key<T> key : keyList) {
            Result.addAll(this.value.get(key.getKey()));
        }
        return Result;
    }

    /**
     * 插件新节点
     *
     * @param key
     * @return true 为成功插入<br> false 插入失败<br> 注：该功能在这一版本未实现<br>
     */
    private boolean InsertKey(Key<T> key) {
        Search(key);
        if (!this.Current.getChilden().get(0).hasNext()) {
            return false;
        } else if (key.compareTo(this.root.getKey().get(0)) < 0) {

            Node node = new Node(key, this.m);
            Node _node = new Node(key, this.m);
            node.setParent(_node);
            return true;
        } else {

            Node node = new Node(key, this.m);
            node.setParent(this.Current);
            this.Current.addChilden(key, node);
            Collections.sort(this.Current.getKey());
            Collections.sort(this.Current.getChilden());
            while (this.Current.getKeyNum() > this.m) {
                Node _node = new Node(key, this.m);
                for (int i = 0; i < m / 2; i++) {
                    _node.addChilden(this.Current.getChilden(i).getKey(i), this.Current.getChilden(i));
                    this.Current.getChilden(i).setParent(_node);
                    this.Current.removeChilden(i);
                    this.Current.removeKey(i);
                }
                _node.setParent(this.Current.getParent());
                Collections.sort(_node.getChilden());
                this.Current.getParent().addChilden(_node.getKey(0), _node);

                this.Current = this.Current.getParent();
            }
            return true;
        }
    }

    /**
     * 查询该关键字是否已经存在<br> B+树不允许关键字重复<br> 所以在对B+树进行插入时需要预先检查插入键值是否已经存在<br>
     *
     * @param KeyWords 关键字
     * @return true 表明该关键字已存在 false 表明关键字不存在
     */
    public boolean Contian(Key<T> KeyWords) {
        this.Current = this.root;
        if (this.Current.getChilden().isEmpty()) {
            while (this.Current.getChilden().get(0).hasNext()) {
                for (int i = 0; i < this.Current.getKey().size(); i++) {
                    Key<T> temp = this.Current.getKey().get(i);
                    int result = KeyWords.compareTo(temp);
                    if (result == 0) {
                        return true;
                    } else if (result < 0) {
                        this.Current = this.Current.getChilden().get((i - 1));
                        break;
                    }
                }
            }
        } else {
            for (int i = 0; i < this.Current.getKey().size(); i++) {
                Key<T> temp = this.Current.getKey().get(i);
                int result = KeyWords.compareTo(temp);
                if (result == 0) {
                    return true;
                } else if (result < 0) {
                    if (!this.Current.getChilden().isEmpty()) {
                        this.Current = this.Current.getChilden().get((i - 1));
                        break;
                    }
                    break;
                }
            }
        }
        return false;
    }
}
